import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
  二叉搜索树的最近公共祖先
* 算法：递归
*

* */
public class Solution_1 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;

        while (true)
        {
            if(p.val< ancestor.val&&q.val<ancestor.val)
            {
                ancestor=ancestor.left;
            }
            else if(p.val>ancestor.val&&q.val>ancestor.val)
            {
                ancestor=ancestor.right;
            }
            else {
                break;
            }
        }
        return ancestor;
    }

}
